package com.algorithm;

public class QuictSort {
    public static void main(String[] args){
        int[] nums = new int[]{2,1};
        int end = nums.length-1;

        //移动 0 value 到nums的最后边
        int temp = 0 ;
        int beg = 0 ;
        while(beg<=end){
            if(nums[beg]==0){
                temp =  nums[end];
                nums[end] = nums[beg];
                nums[beg] = temp ;
                end --;
            }
            beg ++ ;
        }
        new QuictSort().sort(nums,0,end);
        for (int a: nums) {
            System.out.println(a);
        }
    }

    private int partition(int[] nums,int beg,int end){
        int key = nums[beg] ;
        while(beg<end){
            while(beg<end && nums[end]>=key){
                end -- ;
            }
            nums[beg] = nums[end];

            while(beg<end && nums[beg]<=key){
                beg ++ ;
            }
            nums[end] = nums[beg];
        }
        nums[end] = key ;
        return end ;
    }

    private void sort(int[] nums ,int beg,int end){
        if(beg>=end){
            return;
        }

        int index = partition(nums,beg,end);
        sort(nums,0,index-1);
        sort(nums,index+1,end);
    }
}
